package com.daji.base_data_structure.Tree.binary_tree;


public class DeleteBST {
    public static void main(String[] args) {
        BinaryTreeAPI binaryTreeAPI = new BinaryTreeAPI();
        TreeNode treeNode = binaryTreeAPI.initBinaryTree(new Integer[]{5, 3, 6, 2, 4, null, 7});
        TreeNode result = deleteNode(treeNode, 3);
        binaryTreeAPI.levelOrderPrint(result);
    }
    //前置知识：二叉搜索树的性质：
    // 中序遍历就是从小到大
    // 整个树最小的结点，就是递归遍历左子树所能达到的最后一个结点
    // 整个树最大的结点，就是递归遍历右子树所能达到的最后一个结点

    //后继结点(记为successor)和前驱结点（记为predecessor）的定义：
    // 该结点的successor：二叉搜索树根据中序遍历(其实就是从小到大排列)，该结点右边的那个数。
    // （其实就是从小到大排列后比该结点大的第一个数字）
    // 该结点的predecessor：二叉搜索树根据中序遍历(其实就是从小到大排列)，该结点左边的那个数。
    // （其实就是从小到大排列后比该结点小的第一个数字）

    //如果找到了该结点，分三种情况
    //1、如果该结点是叶子结点，直接删除即可
    //2、如果该节点有右结点，将该节点的后继结点(记为successor)提到该节点的位置进行覆盖。
    //   进行覆盖之后, successor重复了。于是想办法将successor删除（递归调用2或3来删除）
    //   套娃这一过程，即可完成删除操作。
    //3、如果该节点只有左结点而没有右结点，那它的后继结点一定在他的上面（由二叉搜索树性质决定）
    //   所以我们可以使用该节点的前驱结点（记为predecessor）提到该节点的位置进行覆盖。
    //   进行覆盖之后，predecessor重复了。于是想办法将predecessor删除（递归调用2或3来删除）
    //   套娃这一过程，即可完成删除操作。


    //难点：如何不用中序遍历二叉树的情况下，更方便地找到该节点的后继结点(successor)，和前驱结点(predecessor)？
    //其实非常之简单，找successor，就是找该结点的右结点（如果有的话），并将该节点的右结点
    //看作是一颗新的二叉搜索树，然后找到该二叉搜索树最小的结点，该结点就是successor
    //体现了找“比我大的最小结点”的思想

    //找predecessor正好相反，就是找该结点的左结点（如果有的话），并将该节点的左结点
    //看作是一颗新的二叉搜索树，然后找到该二叉搜索树最大的结点，该结点就是predecessor
    //体现了找“比我小的最大结点”的思想

    //注意：该方法找successor和predecessor，只适用于左/右结点存在的情况。如果不存在，请老实地使用中序遍历！
    //注意：该方法找successor和predecessor，只适用于左/右结点存在的情况。如果不存在，请老实地使用中序遍历！
    //注意：该方法找successor和predecessor，只适用于左/右结点存在的情况。如果不存在，请老实地使用中序遍历！
    public static TreeNode deleteNode(TreeNode root, int key) {
        //先找到这个结点再说。如果找不到，直接返回原来的树
        TreeNode workNode = root;    //工具结点
        TreeNode targetNode = null;  //找到的该结点
        while (workNode != null) {
            if (key < workNode.val) {
                workNode = workNode.left;
            } else if (key > workNode.val) {
                workNode = workNode.right;
            } else { //root.val == key
                targetNode = workNode;  //已经找到该节点
                break;
            }
        }
        if (targetNode == null) {    //二叉树根本没有该结点，直接返回原本的树即可
            return root;
        }
        //情况一：该节点是叶结点,直接删除
        if (targetNode.left==null && targetNode.right==null){
            if (targetNode.val == root.val){    //边界检查：根节点就是叶子结点，直接return null
                return null;
            }
            deleteLeaf(root,targetNode);
            return root;
        }
        //情况二：如果该节点有右结点，将该节点的后继结点(记为successor)提到该节点的位置进行覆盖，并递归删除
        if (targetNode.right!=null){
            TreeNode successor = findSuccessor(targetNode);
            coverNode(targetNode,successor);
            targetNode.right = deleteNode(targetNode.right, successor.val); //递归删除
        }else if (targetNode.right==null && targetNode.left!=null){ //情况三：如果该节点只有左结点而没有右结点，使用该节点的前驱结点（记为predecessor）提到该节点的位置进行覆盖。
            TreeNode predecessor = findPredecessor(targetNode);
            coverNode(targetNode,predecessor);
            targetNode.left =  deleteNode(targetNode.left, predecessor.val); //递归删除
        }

        return root;
    }

    //覆盖结点. oriNode指要被覆盖的结点，newNode指代替它的结点
    private static void coverNode(TreeNode oriNode, TreeNode newNode) {
        oriNode.val = newNode.val;
    }

    //直接删除叶结点
    private static void deleteLeaf(TreeNode root, TreeNode targetNode) {
        TreeNode workNode = root;    //工具结点
        while (true){
            if (targetNode.val < workNode.val){
                if (workNode.left.val!= targetNode.val){
                    workNode = workNode.left;
                }else {
                    workNode.left = null;   //如果相等则删除该结点
                    return;
                }
            }else {
                if (workNode.right.val!= targetNode.val){
                    workNode = workNode.right;
                }else {
                    workNode.right = null;   //如果相等则删除该结点
                    return;
                }
            }
        }
    }

    private static TreeNode findSuccessor(TreeNode node) {
        if (node.right == null) {  //如果没有右结点，该节点的successor肯定在它上面，所以用该方法是找不到的。
            return null;
        }
        node = node.right;
        //下面的代码其实就是调用findMin方法找最小结点
        while (true){
            if (node.left != null) {
                node = node.left;
            }else {
                break;
            }
        }
        return node;
    }

    private static TreeNode findPredecessor(TreeNode node) {
        if (node.left == null) {
            return null;
        }
        node = node.left;
        //下面的代码其实就是调用findMax方法找最大结点
        while (true){
            if (node.right != null) {
                node = node.right;
            }else {
                break;
            }
        }
        return node;
    }

}
